package 动态规划.背包And分组And切割问题系列;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/6/4 22:09
 */
public class lc2551 {
    /*
     这里主要思考的 是，  按照 ， **子数组分组的** 思想，来做的话，
     能不能进行斜率 优化，
     以及下面的代码为啥能 正确， 巧合？ ， 难道分组，有一些 新的思想，在 里面？
     */


/*
    这个采用的是 01 背包的 解法, 居然 是正确的 !(算法是正确的, 超时!)
    但是 我感觉有点巧合的存在!
    f(i,k) 表示的 含义: 从 i ~ len ,放入 k个 背包(每个背包至少 一个 珠子) 的最大(小)分数
    - 如果 把 i 归入 k 背包中的 话
    调用 f(i + 1,k) : 背包不变, 继续 向下个 珠子, 做抉择!
            - 如果 i 号珠子 ,归入当前 背包, 并且 i + 1 开始 放入 k - 1 背包中
    f(i + 1,k - 1) + weight[i] + weight[i + 1]

    这种考虑 就有问题, 我感觉只不过是 ,正确的 代码 刚好 是 求相邻的 和,
    与这种 碰巧了吧

    */
        /*
    class Solution {
private:
    long long bagProblem(vector<int>& weights, vector<long long>& dp, bool flag) {
        int bagWeight = dp.size() - 1;
        for (int i = 1; i < weights.size(); i++) {
            for (int j = bagWeight; j >= 1; j--) {
                if (flag) dp[j] = max(dp[j], dp[j - 1] + weights[i] + weights[i - 1]);
                else dp[j] = min(dp[j], dp[j - 1] + weights[i] + weights[i - 1]);
            }
        }
        return dp[bagWeight];
    }
public:
    long long putMarbles(vector<int>& weights, int k) {
        vector<long long> dp(k, 0);
        for (int i = 1; i < k; i++) dp[i] = INT_MIN;
        long long maxScore = bagProblem(weights, dp, true);
        for (int i = 1; i < k; i++) dp[i] = INT_MAX;
        long long minScore = bagProblem(weights, dp, false);
        return maxScore - minScore;
    }
};
     */
}
